Дерево (граф)

граф
Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа.
[ ГОСТ Р 52002-2003]

граф
Основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны — как совокупность двух множеств: множества элементов x ? X и множества соответствий, отношений между этими элементами t ? T. С другой стороны — как некая геометрическая схема, тогда элементы множества X будут точками (их называют вершинами x), а соответствия t — отрезками (ребрами), соединяющими элемент x с элементами, которые с ним связаны. В соответствии с этим существуют и два подхода к определению предмета теории графов: теоретико-множественный и геометрический. Граф g = (X, T) называется конечным, если число его вершин конечно. Практически изучаются только конечные Г., бесконечные же пока представляют лишь теоретический интерес. Г. называется ориентированным или направленным, если всякая пара точек упорядочена, т.е. соединяющее их ребро имеет начало и конец (тогда оно называется дугой). Две точки, определяющие ребро или дугу, называются смежными. Смежными называются и две дуги, если они имеют общую вершину. Последовательность дуг, при которой конец одной дуги является началом другой, называется путем. В случае ненаправленного Г. применяют термин цепь. Если начало и конец пути совпадают, образуется контур или цикл. Г. называется связным, если для каждой пары вершин существует соединяющая их цепь или путь (последовательность ребер). В противном случае он называется несвязным. Г. может разделяться на подграфы, причем связный подграф называется компонентой исходного Г. В экономике особенно широко используются два вида Г.: дерево (см. Дерево целей, Дерево решений) и сеть (см. Сетевое планирование и управление). Для описания Г. часто используется квадратная матрица, именуемая матрицей смежности. У нее как строки, так и столбцы отвечают вершинам Г. (i, j = 1, 2, …, n), а элемент rij несет информацию о ребрах, соединяющих произвольные вершины xi и xj. Например, можно обозначить наличие ребра между ними единицей, а отсутствие — нулем. Это называется матричное представление рассматриваемого Г. Для графа, показанного на рис. Г.2, имеем матрицу: Рис. Г.2 Граф
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика
• электротехника, основные понятия

Синонимы

• граф электрической цепи

EN

• graph

дерево (в теории графов)
В теории графов ? связный граф без циклов, обладающий следующими основными свойствами (которые математически эквивалентны): если за n принять число вершин (элементов графа), то он содержит ровно n — 1 ребро, не имеет циклов; если добавить ребро, соединяющее две несмежные вершины, то образуется один цикл; при удалении любого ребра граф становится несвязным; каждая пара вершин соединяется одной и только одной цепью. Исходная вершина называется корнем, пути от нее к крайним вершинам — ветвями. Примеры см. в статьях: Дерево игры, Дерево решений, Дерево целей.
[ http://slovar-lopatnikov.ru/]

Тематики

• экономика

EN

• tree

дерево решений
Граф - схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Ветви дерева отображают различные события, которые могут иметь место, а узлы (вершины) - состояния, в которых возникает необходимость выбора.
[ОАО РАО "ЕЭС России" СТО 17330282.27.010.001-2008]

дерево решений
Способ представления процесса принятия решения, имеющий вид ответов на серию вопросов, образующих древовидную структуру.
[ http://www.morepc.ru/dict/]

дерево решений
Граф, схема, отражающая структуру задачи оптимизации многошагового процесса принятия решений. Применяется в динамическом программировании и в других областях для анализа решений, структуризации проблем. Ветви дерева отображают различные события, которые могут иметь место, а узлы (вершины) - состояния, в которых возникает необходимость выбора. Причем узлы различны — в одних выбор из некоторого набора альтернатив осуществляет сам решающий (руководитель, лицо, принимающее решения), в других выбор от него не зависит. В таких случаях говорят, что выбор делает «природа», а руководитель может только оценить вероятность того или иного ее «решения». Д.р. применяется тогда, когда количество альтернатив и количество шагов принятия решений ограниченно (конечно). Принцип использования этого метода покажем на простом примере. Предположим, возникла необходимость построить цех для выпуска новой продукции. Можно построить большой цех — мощностью 200 тыс. т продукции в год и стоимостью 1 млрд. руб. Если спрос на продукт будет большой, завод получит прибыль в 1 млрд. руб., строительство цеха окупится за год. Но если спрос будет меньше, допустим, только на 100 тыс. т, то прибыль составит уже лишь 500 млн. руб.: если же товар совсем «не пойдет», завод понесет убытки в 1 млрд. руб. Возникает второй вариант: строить меньший цех — мощностью 100 тыс. т и стоимостью 500 млн. руб. Тогда при высоком и малом спросе прибыль будет равна 500 млн. руб., а при отсутствии спроса убыток составит 500 млн. руб. Все это можно показать на схеме (рис.Д.2). Получается шесть возможных вариантов последствий двух возможных решений. Какое же из них выбрать? Это зависит от вероятностей того или иного состояния будущего спроса: чем больше вероятность высокого спроса, тем разумнее, очевидно, будет предпочесть вариант строительства крупного цеха. Но задача осложнится еще больше, если сформулировать ее иначе: спрос на продукцию будет, как предполагается, расти постепенно. Что при этом лучше: строить сразу большой цех или же малый, но через некоторое время (если спрос действительно окажется большим) реконструировать его? Такие задачи также решаются методом Д.р. Приведенный пример характерен для структуры задач динамического программирования с конечным числом решений. Как видим, здесь сначала осуществлялся выбор последнего по времени решения, а затем, при движении в направлении, обратном течению времени, выбирались все остальные решения вплоть до исходного (см. Беллмана принцип оптимальности). Рис. Д.2 Дерево решений Спрос: б — большой, м — малый, о — отсутствие спроса
[ http://slovar-lopatnikov.ru/]

Тематики

• информационные технологии в целом
• экономика

EN

• decision tree

дерево целей
—
[Л.Г.Суменко. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.]

дерево целей
В программно-целевых методах планирования и управления — граф, схема, показывающая членение общих (генеральных) целей плана или программы на подцели, последних — на подцели следующего уровня и т.д. (дерево — это связный граф, выражающий соподчинение и взаимосвязи элементов; в данном случае такими элементами являются цели и подцели). Представление целей начинается с верхнего яруса, дальше они последовательно разукрупняются. Причем основным правилом разукрупнения целей является полнота: каждая цель верхнего уровня должна быть представлена в виде подцелей следующего уровня исчерпывающим образом, т.е. так, чтобы объединение понятий подцелей полностью определяло понятие исходной цели. На рис.Д.3. показан фрагмент примерного Д. ц. долгосрочной программы развития региона. Д. ц., направленное на решение такой народнохозяйственной и социальной задачи как подъем отставшего в своем развитии региона (генеральная цель программы), может включать подцели первого яруса: повышение благосостояния населения, развитие производительных сил, экологическое оздоровление и др. Одна из перечисленных целей — повышение благосостояния (на рис. Д.3. обозначенная цифрой 4), в свою очередь, на втором ярусе подразделяется на «материальное благосостояние» (4.1) и «социальное благосостояние» (4.2), а на третьем ярусе подцель «материальное благосостояние» расшифровывается как целая серия целей: «питание», «одежда», «жилой комплекс» и т.д. Разумеется, это очень условный пример. Но на нем можно познакомиться с основными понятиями, применяемыми в целевом планировании. Понятие «состязательность целей» означает, что достижение одной цели затрудняет достижение другой. Если каким-то способом получить численный коэффициент состязательности между ними, это позволит включить их в математическую программу расчетов по Д. ц. (например, расчетов количества времени, необходимого для достижения глобальной цели при разных вариантах распределения ресурсов между ними). Коэффициент взаимной поддержки целей, напротив, определяет, в какой мере достижение одной цели способствует достижению другой. Особенно важны коэффициенты значимости целей. Они определяются экспертным путем и показывают, какая из целей важнее, чем можно поступиться при необходимости для их достижения, и наоборот, на что надо обратить большее внимание, выделить больше ресурсов. От полноты информации, заключенной в Д. ц., в решающей степени зависит качество всей последующей работы — оценки программ, их прогнозируемых следствий, оценки планов, разработка всей системы деятельности по созданию условий для реализации планов и программ. Рис. Д.3. Фрагмент дерева целей 0 — генеральная цель: «Ускорение развития рассматриваемого региона»; 4 — «Повышение благосостояния населения»; 4.1 — «Материальное благосостояние»; 4.2 — «Социальное благосостояние»; 4.1.1 — «Улучшение природно-биологической среды жизни»; 4.1.2 — «Питание»; 4.1.3 — «Одежда»…; 4.1.3.1 — «Обувь» и т. д.
[ http://slovar-lopatnikov.ru/]

Тематики

• информационные технологии в целом
• экономика

EN

• objective tree
• relevance tree

древовидный граф
дерево
—
[Л.Г.Суменко. Англо-русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.]

Тематики

• информационные технологии в целом

Синонимы

• дерево

EN

• tree graph